4Sorting Algorithms 排序问题

排序问题在早期时，由于电脑储存有限，如何排序不太重要。但如今随着信息的储存越来越多，排序也变得越来越重要了

学习排序算法之前的前期准备。

  1. Terminology 术语

A 是一个要被排序的集合，A[i] 和 ai 都代表集合的 ith 元素，通常，我们认为第一个元素是 A[0]，a0，0th。我们用 A[low,low+n) 代表第 A[low]…A[low+n-1] 共 n 个元素，A[low,low+n] 则有 n 个元素。

如果要为一个集合排序，如果给出条件是 if A[i]<A[j]，则 i<j，则有重复元素就扎堆相邻即可。注意排序后的序列一定是顺序不同的排序前序列。
2. Representation 数据存储

数据有可能在内存（RAM）或者外存（二级存储器）里或者磁带光盘（三级存储器），无疑级数越多需要的加载时间就越多。

内存中的信息存储采取以下两种形式之一，基于指针的存储 (pointer-based) 和基于值 (value-based) 的存储。

基于指针的的存储，数组里储存的是一个个指针，指针指向了数据的真实值，这样方便修改顺序，适合 RAM。

基于数值的存储，将 n 个元素打包存储在一个固定空间 s 里，更适合于二级存储和三级存储。会用连续的相同的内存单元存储数据，比如都用 s=5 个字母的空间存储一群英文单词，则 A[r*s+c] 就是第 r 个单词的第 c 个字母，A[i*s,(i+1)*s) 就是第 i 个单词，有的单词只有三个字母，这样存储也对导致出现一些空区域，这是必要的，因为如果不统一结构，将无法读取数据。

第二存储器外存，是基于值的存储，单位是 byte 字节，1byte=8bit，对于内存设计的算法一样可以用在磁盘（第二存储器）数据上，只是需要加一些传输函数，并且浪费一些输入输出间。Merge Sort 归并排序尤其适合储存在磁盘的数据。
3. Comparable Elements 可排序的元素

想为元素排序，需要编码准则和排序准则。字符编码标准 http://www.unicode.org/versions/latest 提供了 UTF-16，用四个字节代表一个字符，包含所有字符；字符排序标准 http://www.unicode.org 提供了所有字符的排序准则。

当要排序的每一个数据都包括很多方面信息时，就要确定主要的排序元素（key value）比如飞机场给飞机的排序，可以根据起飞时间；可以根据城市。
4. Stable Sorting 稳定排序

如果比较函数（comparator function 简写 cmp）比较两个相等的元素，那么他们最终的顺序应该与开始的相同。那么保证了以上这一点的算法，我们称它稳定。

例子是一个已经按时间顺序排列的飞机时刻表，再用一个 cmp 按照目的地排序，排序结果是目的地相同的班次，也同样按照时间顺序排列了，说明 cmp 是一个稳定排序（没有打乱相同目的地的时间顺序）
5. Criteria for Choosing a Sorting Algorithm 选择排序算法的标准

序列很短——插入排序 Insertion Sort

序列本来就马上排好了——插入排序

担心最坏的情况——堆排序 Heap Sort

平均情况最好——快速排序 Quicksort

输入数据均匀分布——桶排序 Buget Sort

希望少写代码——插入排序

希望排序稳定——归并排序 Merge Sort

Transposition Sorting 换位排序
早期算法，通过交换来排序，包括 Selection Sort（选择排序法）和 Bubble Sort（冒泡排序）等。他们都被 Insertion Sort（插入排序）超越，下面我们介绍插入排序。

  1. 插入排序 Insertion Sort